/**
* @description: 998. 最大二叉树 II
* @author hewei
* @date 2022/8/30 14:13
* @version 1.0
*/

public class InsertIntoMaxTree {

    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        TreeNode target = new TreeNode(val);
        if (val > root.val) {
            target.left = root;
            return target;
        }
        TreeNode temp = root;
        while (root.right != null && root.right.val > val) root = root.right;
        if (root.right == null) {
            root.right = target;
            return temp;
        }
        target.left = root.right;
        root.right = target;
        return temp;
    }
}
